class Solution:
	# @param board, a 9x9 2D array
	# Solve the Sudoku by modifying the input board in-place.
	# Do not return any value.
	def solveSudoku(self, board):
		def cross(A, B):
			return [a+b for a in A for b in B]

		digits = '123456789'
		rows = 'ABCDEFGHI'
		cols = digits
		squares = cross(rows, cols)
		unitlist = [cross(rows, c) for c in cols] + [cross(r, cols) for r in rows] + \
			[cross(rs, cs) for rs in ('ABC','DEF','GHI') for cs in ('123','456','789')]
		units = dict((s, [u for u in unitlist if s in u]) for s in squares)
		peers = dict((s, set(sum(units[s],[]))-set([s])) for s in squares)

		def parse_grid(grid):
		    """Convert grid to a dict of possible values, {square: digits}, or
		    return False if a contradiction is detected."""
		    ## To start, every square can be any digit; then assign values from the grid.
		    values = dict((s, digits) for s in squares)
		    for s,d in grid_values(grid).items():
		        if d in digits and not assign(values, s, d):
		            return False ## (Fail if we can't assign d to square s.)
		    return values

		def grid_values(grid):
		    "Convert grid into a dict of {square: char} with '0' or '.' for empties."
		    s_grid = ''.join(sum(grid,[]))
		    chars = [c for c in s_grid if c in digits or c in '0.']
		    assert len(chars) == 81
		    return dict(zip(squares, chars))

		def assign(values, s, d):
		    """Eliminate all the other values (except d) from values[s] and propagate.
		    Return values, except return False if a contradiction is detected."""
		    other_values = values[s].replace(d, '')
		    if all(eliminate(values, s, d2) for d2 in other_values):
		        return values
		    else:
		        return False

		def eliminate(values, s, d):
		    """Eliminate d from values[s]; propagate when values or places <= 2.
		    Return values, except return False if a contradiction is detected."""
		    if d not in values[s]:
		        return values ## Already eliminated
		    values[s] = values[s].replace(d,'')
		    ## (1) If a square s is reduced to one value d2, then eliminate d2 from the peers.
		    if len(values[s]) == 0:
			return False ## Contradiction: removed last value
		    elif len(values[s]) == 1:
		        d2 = values[s]
		        if not all(eliminate(values, s2, d2) for s2 in peers[s]):
		            return False
		    ## (2) If a unit u is reduced to only one place for a value d, then put it there.
		    for u in units[s]:
			dplaces = [s for s in u if d in values[s]]
			if len(dplaces) == 0:
			    return False ## Contradiction: no place for this value
			elif len(dplaces) == 1:
			    # d can only be in one place in unit; assign it there
		            if not assign(values, dplaces[0], d):
		                return False
		    return values

		def solve(grid): return search(parse_grid(grid))

		def search(values):
		    "Using depth-first search and propagation, try all possible values."
		    if values is False:
		        return False ## Failed earlier
		    if all(len(values[s]) == 1 for s in squares): 
		        return values ## Solved!
		    ## Chose the unfilled square s with the fewest possibilities
		    n,s = min((len(values[s]), s) for s in squares if len(values[s]) > 1)
		    return some(search(assign(values.copy(), s, d)) 
				for d in values[s])

		def some(seq):
		    "Return some element of seq that is true."
		    for e in seq:
		        if e: return e
		    return False

		def alter(grid, values):
			v = solve(grid)
			for i in xrange(9):
				for j in xrange(9):
					key = rows[i] + cols[j]
					grid[i][j] = values[key]

		val = solve(board)
		alter(board, val)


if __name__ == '__main__':
	bo = ['53..7....',
		  '6..195...',
		  '.98....6.',
		  '8...6...3',
		  '4..8.3..1',
		  '7...2...6',
		  '.6....28.',
		  '...419..5',
		  '....8..79']
	b = [list(l) for l in bo]
	so = Solution()
	so.solveSudoku(b)
	for i in b:
		print i














